package com.linked;


/**
 * @className: com.linked.LinkedList
 * @description: 单链表实现LinkedList(线程不安全)
 * @author: tong.li
 * @createTime: 2022/6/15 20:12
 * @copyright: Tongcheng-Elong Holdings Limited
 */
public class LinkedList<T> {

    /**
     * 头节点
     */
    private Node<T> head;

    /**
     * 链表存储长度
     */
    private int size = 0;

    /**
     * 空参构造并初始化头节点
     */
    public LinkedList() {
        this.head = new Node<>();
    }

    /**
     * 返回链表存储长度
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断链表是否为空
     * @return  true-为空
     */
    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 获取头节点的值
     * @return
     */
    public T getFirst() {
        return this.head == null ? null : head.data;
    }

    /**
     * 获取尾节点的值
     * @return
     */
    public T getLast() {
        Node<T> lastNode = this.getLastNode();
        return lastNode == null ? null : lastNode.data;
    }


    /**
     * 获取头节点
     * @return
     */
    private Node<T> getFirstNode() {
        return this.head;
    }



    /**
     * 获取尾结点
     * @return
     */
    private Node<T> getLastNode() {
        // 需要定义额外指针进行移动，获取节点，不能修改原有节点
        Node<T> last = this.head;
        while (last.next != null) {
            // 移动链表尾结点
            last = last.next;
        }
        return last;
    }

    /**
     * 清空链表
     */
    public void clear() {
        // 清空数据域
        this.head.data = null;
        // 清空指针域
        this.head.next = null;
        // 将链表大小置为0
        this.size = 0;
    }


    /**
     * 插入元素(默认尾插)
     * @param data
     * @return
     */
    public boolean add(T data) {
        return this.addLast(data);
    }


    /**
     * 尾插具体实现
     * @param data
     * @return
     */
    private boolean addLast(T data) {
        // 若节点为空，那么当前节点就是头节点,同样也是尾结点
        if (isEmpty()) {
            this.head.data = data;
            this.incr();
            return true;
        }
        // 构建当前节点
        Node<T> curr = new Node<>(data);
        // 找到链表尾节点
        Node<T> last = getLastNode();
        // 将当前节点置为尾结点
        last.next = curr;
        // 添加完成后，变更链表长度值
        this.incr();
        return true;
    }



    /**
     * 头插具体实现
     * @param data
     * @return
     */
    public boolean addFirst(T data) {
        // 若节点为空，那么当前节点就是头节点,同样也是尾结点
        if (isEmpty()) {
            this.head.data = data;
            this.incr();
            return true;
        }
        Node<T> curr = new Node<>(data);
        // 头插稍微简单些，获取到头节点，直接追加到头节点前面即可
        Node<T> first = getFirstNode();
        curr.next = first;
        // 追加完成后，当前节点就变成了head节点，这里千万要注意
        this.head = curr;
        // 添加完成后，变更链表长度值
        this.incr();
        return true;
    }

    /**
     * 构建新节点，并将新节点插入到指定位置
     * @param index
     * @param data
     * @return
     */
    public boolean add(int index, T data) {
        // 若节点为空，那么当前节点就是头节点,同样也是尾结点
        if (isEmpty()) {
            this.head.data = data;
            this.incr();
            return true;
        }
        // 获取index所在的节点作为当前要构建节点的前驱节点
        Node<T> pre = getNode(index);
        // 备份下一个节点
        Node<T> next = pre.next;
        // 构建当前节点
        Node<T> curr = new Node<>(data);
        // 链接当前节点
        pre.next = curr;
        // 当前节点下一个节点就是备份节点
        curr.next = next;
        return true;
    }


    /**
     * 根据索引查找对应的节点
     * @param index  索引从0开始
     * @return
     */
    private Node<T> getNode(int index) {
        // 校验索引合法性
        checkIndex(index);
        if (isEmpty()) {
            return null;
        }
        // 存放查找到的节点,index从0开始
        Node<T> node = head;
        for (int i = 0; i < index && node != null; i++) {
            node = node.next;
        }
        return node;
    }

    public T get(int index) {
        Node<T> node = getNode(index);
        return node == null ? null : node.data;
    }


    /**
     * 修改指定索引的节点值
     * @param index
     * @param data
     */
    public void set(int index, T data) {
        Node<T> node = getNode(index);
        node.data = data;
    }

    /**
     * 返回链表中首次出现指定数据元素的索引位。若没有，返回-1
     * @param data
     * @return
     */
    public int indexOf(T data) {
        int index = -1;
        Node<T> node = this.head;
        for (int i = 0; node != null ; i++) {
            if (node.data.equals(data)) {
                // 找到返回当前索引号
                return i;
            }
            // 移动到下一个节点
            node = node.next;
        }
        return index;
    }

    /**
     * 删除指定位置的节点并返回删除节点的值
     * @param index
     * @return
     */
    public T remove(int index) {
        // 校验索引合法性
        checkIndex(index);
        if (isEmpty()) {
            // 链表为空，那你删个毛啊
            throw new UnsupportedOperationException("空链表，删除个毛啊你~");
        }
        if (index == 0) {
            T data = head.data;
            // 删除头节点
            head = head.next;
            // 要更新size的值
            decr();
            return data;
        }
        // 要删除节点的前驱节点
        Node<T> pre = getNode(index - 1);
        // 当前要删除的节点
        Node<T> curr = pre.next;
        pre.next = curr.next;
        // 删除后，size--
        decr();
        return curr.data;
    }


    /**
     * 链表反转
     */
    public void reverse() {
        // 存放前节点
        Node<T> pre = null;
        Node<T> next;
        while (head != null) {
            // 把当前节点的下一个引用备份出来
            next = head.next;
            // 将当前节点引用指向上一个地址
            head.next = pre;
            // 把当前节点給前置节点，pre往后移，方面后续操作
            pre = head;
            // 处理完毕后，移位
            head = next;
        }
        // head指针最终会移动到尾节点,不再是头节点,即head.next = null,pre节点才是最新的头节点
        head = pre;
    }


    /**
     * 给定两个链表，将链表进行相加(从左往右-个十百千万)
     *   例：4 -> 3 -> 6
     *    + 2 -> 5 -> 3
     *    ---------------
     *      6 -> 8 -> 9
     *  分析：
     *     1. 长链表元素有 AND 短链表元素有 = 长链表数据域 + 短链表数据域 + 进位信息
     *     2. 长链表元素有 AND 短链表元素有 = 长链表数据域 + 进位信息
     *     3. 长链表元素无 AND 短链表元素无 = 只剩下进位信息
     *  注意： 这个泛型只能数字，因为只有数字才能相加
     * @param first
     * @param second
     */
    public static LinkedList<Integer> plusTwoLinked(LinkedList<Integer> first, LinkedList<Integer> second){
        // 若要加的链表为空，那还加毛啊
        if (first == null || first.isEmpty()) {
            return second;
        }
        if (second == null || second.isEmpty()) {
            return first;
        }
        // 分别找出长短链表，先根据长度判断长链表
        LinkedList<Integer> longLinked = first.size >= second.size ? first : second;
        // 若第一个链表就是长链表，那么第二个节点就是短链表
        LinkedList<Integer> shortLinked = first == longLinked ? second : first;
        // 定义两个指针，默认指向指针的头部，用于移动移动上面两个长短链表
        Node<Integer> curLongNode = longLinked.head;
        Node<Integer> curShortNode = shortLinked.head;
        // 存放进位信息，没有进位，进位就是0
        int carry = 0;
        // 存放计算的值
        int curCalValue = 0;
        // 这里再定义一个指针，记住尾节点，最终返回的肯定是长链表
        Node<Integer> last = curLongNode;
        // 先移动短链表，只有短链表移动完，长链表的操作就简化了
        while (curShortNode != null) {
            // 当前节点值=长链表的data + 短链表的data + 进位信息
            curCalValue = curLongNode.data + curShortNode.data + carry;
            // 將余数存放在结果里
            curLongNode.data = (curCalValue % 10);
            // 更新进位信息，加法每次进位只能是1
            carry = curCalValue / 10;
            // 記錄最后一个节点，如果不记住，那么curLongNode最终会移动到null
            last = curLongNode;
            // 长短链表往后移动
            curLongNode = curLongNode.next;
            curShortNode = curShortNode.next;
        }
        // 到这里只剩下长链表剩余节点和进位信息
        while (curLongNode != null) {
            // 当前节点值=长链表的data + 进位信息
            curCalValue = curLongNode.data + curShortNode.data + carry;
            // 將余数存放在结果里
            curLongNode.data = (curCalValue % 10);
            // 更新进位信息，加法每次进位只能是1
            carry = curCalValue / 10;
            // 記錄最后一个节点，如果不记住，那么curLongNode最终会移动到null
            last = curLongNode;
            //长链表往后移
            curLongNode = curLongNode.next;
        }
        // 到这里就只剩下进位信息了，那么处理一下进位就可以了
        if (carry != 0) {
            // 多余一个进位信息，那么新建个进位节点，追加到
            last.next = new Node<>(carry);
        }
        // 因为将最终的结果放在长链表里。我们返回长链表就可以了
        return  longLinked;
    }


    /**
     * 两个有序链表合并(按顺序串起来)
     *  例： 1 -> 3 -> 3 -> 5 -> 7
     *      2 -> 2 -> 3 -> 3 -> 7
     *   --------------------------
     *     1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 5 -> 7
     * @param first
     * @param second
     * @return
     */
    public static LinkedList<Comparable> combineTwoLinked(LinkedList<Comparable> first, LinkedList<Comparable> second){
        // 若要加的链表为空，那还串个毛啊
        if (first == null || first.isEmpty()) {
            return second;
        }
        if (second == null || second.isEmpty()) {
            return first;
        }
        // 判断两个链表头节点的元素大小，确定最终返回的节点
        LinkedList<Comparable> linked = first.head.data.compareTo(second.head.data) <= 0 ? first : second;
        // 定义两个指针，分别移动两个链表, 因为上一行代码已经比较过头节点的第一个元素了，那么就从较小节点下一个节点开始
        Node<Comparable> curr1 = linked.head.next;
        Node<Comparable> curr2 = linked == first ? second.head : first.head;
        // 再定义一个变量，记录当前节点的前继节点
        Node<Comparable> pre = linked.head;
        // 遍历节点
        while (curr1 != null && curr2 != null) {
            if (curr1.data.compareTo(curr2.data) <= 0) {
                // 如果curr1节点小于等于curr2节点，那么串起来：谁小谁移动
                pre.next = curr1;
                curr1 = curr1.next;
            } else {
                // 更新pre前节点
                pre.next = curr2;
                // 谁小谁往后移动，curr2往后移动
                curr2  = curr2.next;
            }
            // pre往后移动
            pre = pre.next;
        }
        // 循环结束后,如果有链表后续还没移动完，那么直接指向未移完的链表即可，谁没走完，那么后面就指向谁
        pre.next = curr1 != null ? curr1 : curr2;
        return linked;
    }


    /**
     * 校验索引合法性
     * @param index
     */
    public void checkIndex(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException(String.format("Index: %s, Size: %s", index, size));
        }
    }



    /**
     * 统一封装：size自增
     * 此处为线程不安全的
     */
    public void incr() {
        this.size++;
    }


    /**
     * 统一封装：size自减
     * 此处为线程不安全的
     */
    public void decr() {
        this.size--;
    }




    @Override
    public String toString() {
        if (isEmpty()) {
            return null;
        }
        return this.head.toString();
    }



    /**
     * 单链表节点
     * @param <T>
     */
    static class Node<T> {

        /**
         * 数据域
         */
        public T data;

        /**
         * 指针域
         */
        public Node<T> next;

        /**
         * 空参构造
         */
        public Node() {
        }

        /**
         * 带有数据域的构造
         * @param data
         */
        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            // 备份引用
            Node<T> head = this;
            while (head != null) {
                // 拼接数据域
                sb.append(head.data).append("->");
                // 移动到下一个节点
                head = head.next;
            }
            // 拼接最后的null并返回
            return sb.append("null").toString();
        }

    }



}
